package com.sub.structure.example;

import java.util.function.BiConsumer;

public class HashTable<K, V> {

    private static class Node<K, V> {
        K key;
        V value;

        Node<K, V> next;

        Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        /**
         * 链表内容展示形式为[(k1:v1)->(k2:v2)->(k3:v3)->null]
         *
         * @return 链表所有元素
         */
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");

            Node<K, V> current = this;
            do {
                sb.append("(").append(current.key).append(":").append(current.value).append(")->");
                current = current.next;
            } while (current != null);

            sb.append("null]");
            return sb.toString();
        }
    }

    private Node<K, V>[] array;

    private final int DEFAULT_INITIAL_CAPACITY = 16;
    private final double LOAD_FACTOR = 0.75;


    public HashTable() {
        array = (Node<K, V>[]) new Node[DEFAULT_INITIAL_CAPACITY];
    }

    private int size = 0;


    /**
     * 用于查询哈希表中键值对的个数
     *
     * @return 键值对个数
     */
    public int size() {
        return size;
    }

    /**
     * 用于判断哈希表是否为空
     *
     * @return 哈希表是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 向哈希表中插入键值对
     *
     * @param key   键
     * @param value 值
     */
    public void put(K key, V value) {

        int index = hash(key, array.length);
        Node<K, V> head = array[index];

        Node<K, V> current = head;
        while (current != null) {
            if (current.key.equals(key)) {
                current.value = value;
                return;
            }
            current = current.next;
        }

        array[index] = new Node<>(key, value, head);
        size++;
        if ((double) size / array.length > LOAD_FACTOR) {
            grow();
        }
    }

    private void grow() {
        Node<K, V>[] newArray = (Node<K, V>[]) new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node<K, V> node = array[i];
            while (node != null) {

                Node<K, V> next = node.next;

                int newIndex = hash(node.key, newArray.length);
                node.next = newArray[newIndex];
                newArray[newIndex] = node;

                node = next;
            }

        }
        array = newArray;

    }

    /**
     * 哈希函数,对key的哈希码进行取余运算
     *
     * @param key    键
     * @param length 数组长度
     * @return 哈希值，作为数组索引
     */
    private int hash(K key, int length) {
        // hashCode方法的返回值为int类型，且可能为负值，所以此处用hashCode与Integer.MAX_VALUE(0111 1111 1111 1111 1111 1111 1111 1111)
        // 进行按位与操作,这会将hashCode的符号位置为0，而其他为保持不变，因此保证结果为正。
        return (key.hashCode() & Integer.MAX_VALUE) % length;
    }

    /**
     * 根据Key查询对应的Value，若指定key不存在则返回null
     *
     * @param key 键
     * @return 值，不存在则为null
     */
    public V get(K key) {
        int index = hash(key, array.length);
        Node<K, V> node = array[index];
        Node<K, V> current = node;
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

    /**
     * 删除指定key对应的键值对
     *
     * @param key 键
     * @return 若存在，则返回key对应的值，否则返回null
     */
    public V remove(K key) {

        int index = hash(key, array.length);

        Node<K, V> head = array[index];

        V result = null;

        if (head != null) {
            if (head.key.equals(key)) {
                result = head.value;
                array[index] = head.next;
                size--;
            } else {
                Node<K, V> pre = head;
                while (pre.next != null) {
                    if (pre.next.key.equals(key)) {
                        result = pre.next.value;
                        pre.next = pre.next.next;
                        size--;
                        break;
                    }
                    pre = pre.next;
                }
            }
        }

        return result;
    }

    /**
     * 对键值对进行遍历
     *
     * @param consumer 对键值对的操作函数
     */
    public void forEach(BiConsumer<K, V> consumer) {
        for (int i = 0; i < array.length; i++) {
            Node<K, V> node = array[i];
            while (node != null) {
                consumer.accept(node.key, node.value);
                node = node.next;
            }
        }
    }
}